#define _CRT_SECURE_NO_WARNINGS
#include"sort.h"

void tmp(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

int GitMindNum(int* arr, int n1, int n2, int n3)
{
	if (arr[n1] > arr[n2])
	{
		if (arr[n2] > arr[n3])
			return n2;
		else
		{
			if (arr[n1] > arr[n3])
				return n3;
			else
				return n1;
		}
	}
	else
	{
		if (arr[n1] > arr[n3])
			return n1;
		else
		{
			if (arr[n2] > arr[n3])
				return n3;
			else
				return n2;
		}
	}
}

void BubbleSort(int* arr, int n)
{
	for (int j = 0; j < n - 1; j++)
	{
		int flag = 1;
		for (int i = 0; i < n - 1 - j; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				tmp(&arr[i], &arr[i + 1]);
				flag = 0;
			}
		}
		if (flag)break;
	}
}

void QuickSort1(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int mind = GitMindNum(arr,arr[left], arr[(left + right) / 2], arr[right]);
	tmp(&arr[mind], &arr[left]);
	int keyi = left;

	int begin = left;
	int end = right;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		tmp(&arr[right], &arr[left]);
	}
	tmp(&arr[left], &arr[keyi]);
	QuickSort1(arr, begin, left - 1);
	QuickSort1(arr, left + 1, end);
}

void QuickSort2(int* arr, int left, int right)
{
	if (left >= right)return;
	int begin = left;
	int end = right;
	int key = arr[left];
	int holei = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[holei] = arr[right];
		holei = right;
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[holei] = arr[left];
		holei = left;
	}
	arr[holei] = key;
	QuickSort2(arr, begin, holei - 1);
	QuickSort2(arr, holei + 1, end);
}

void QuickSort3(int* arr, int left, int right)
{
	if (left >= right)return;
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi]&&++prev!=cur)
			tmp(&arr[cur], &arr[prev]);
		cur++;
	}
	tmp(&arr[keyi], &arr[prev]);
	QuickSort3(arr, left, prev - 1);
	QuickSort3(arr, prev + 1, right);
}